package 区间;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 452. 用最少数量的箭引爆气球
 *
 * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
 *
 * 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
 *
 * 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
 *
 *  思路： 贪心算法，
 *  1：排序：首先，我们可以将所有气球的区间按照结束位置 x_end 进行升序排序。这样做的目的是让我们能够优先处理结束较早的气球，从而尽可能多地用一支箭引爆多个气球。
 *  2：贪心算法：我们从第一个气球开始，射出一支箭在它的结束位置 x_end。然后，我们检查下一个气球的开始位置 x_start 是否小于等于当前箭的位置。
 *  如果是，说明这支箭也可以引爆这个气球，我们继续检查下一个气球；如果不是，说明需要再射出一支箭，并更新箭的位置为当前气球的结束位置。
 *  3： 重复步骤2，直到结束
 */
public class L_452 {
    public int findMinArrowShots(int[][] points) {
        if(points.length == 0){
            return 0;
        }
        // 按Xend进行排序
        Arrays.sort(points, Comparator.comparingInt(a -> a[1]));
        // 默认箭的数量为1，至少需要一支箭
        int arrow = 1;
        // 第一支箭的位置
        int arrowPos = points[0][1];
        // 循环遍历数组
        for (int i = 1; i < points.length; i++) {
            // 如果第一支箭的位置小于当前气球的开始值，则证明需要再射出一支箭，并且更新箭的位置为当前气球的结束位置
            if(arrowPos < points[i][0]){
                arrow++;
                arrowPos = points[i][1];
            }
        }
        return arrow;
    }
}
